Fictitious play is a simple and widely studied adaptive heuristic for playingrepeated games. It is well known that fictitious play fails to be Hannanconsistent. Several variants of fictitious play including regret matching,generalized regret matching and smooth fictitious play, are known to be Hannanconsistent. In this note, we consider sampled fictitious play: at each round,the player samples past times and plays the best response to previous moves ofother players at the sampled time points. We show that sampled fictitious play,using Bernoulli sampling, is Hannan consistent. Unlike several existing Hannanconsistency proofs that rely on concentration of measure results, ours insteaduses anti-concentration results from Littlewood-Offord theory.
展开▼
